#include "string_array.h"

using namespace std;

myStr::myStr(const char* ch) {
    length = 0;
    for (length = 0; ch[length]; length++);
    data = new char[length];
    
    next = new int[length];
    nextVal = new int[length];
    for (int i = 0; i < length; i++) {
        data[i] = ch[i];
    }
    
}

myStr::myStr(const int&l) {
    length = l;
    data = new char[length];
    next = new int[length];
    nextVal = new int[length];
    
}

void myStr::kmp_next() {
    next[0] = 0;
    if (length >= 2) {
        next[1] = 1;
    }
    if (length >= 3) {
        for (int i = 2; i <= length - 1; i++) {
            int same = 0;
            for (int j = 1; j < i; j++) {
                int p=0;
                for (int k = 1; k <= j; k++) {
                    if ((data[k - 1]) == data[i - j + k - 1]) {
                        p++;
                    }
                }
                if (p == j) {
                    same = p;
                }
            }
            next[i] = same + 1;
        }
    }
}
myStr::~myStr(){
    
}

void myStr::kmp_nextVal() {
    kmp_next();
    nextVal[0] = 0;
    for (int i = 1; i < length; i++) {
        if (data[i] != data[next[i] - 1]) {
            nextVal[i] = next[i];
        }
        if (data[i] == data[next[i] - 1]) {
            nextVal[i] = nextVal[next[i]-1];
        }
    }
}
int simpleMatch(const myStr&s, const myStr&t) {
    int ls = s.length;
    int lt = t.length;
    for (int i = 0; i <= ls - lt; i++) {
        int j = 0;
        for (j = 0; j <= lt - 1; j++) {
            if (s.data[i + j] != t.data[j])
                break;
        }
        if (j == lt)
            return (i + 1);
    }
    return -1;
}
int kmpMatch(const myStr&s, const myStr&t) {
    int i = 0;
    int j = 0;
    myStr nt = t;
    nt.kmp_nextVal();
    while (i < s.length && j < t.length) {
        if (s.data[i] == t.data[j]) {
            i++;
            j++;
        }
        else {
            if (j > 0) {
                j = nt.nextVal[j - 1];
            }
            
        }
        if (j == 0)
            i++;
        
    }
    if (j == t.length)
        return(i - t.length+1);
    else return -1;

}
bool replaceStr(myStr&s, const int&start, const myStr&t, const myStr&v) {
    int ls = s.length;
    int lt = t.length;
    int lv = v.length;
    for (int i = start-1; i <= ls - lt; i++) {
        int j = 0;
        for (j = 0; j <= lt - 1; j++) {
            if (s.data[i + j] != t.data[j])
                break;
        }
        if (j == lt) {
        int lns = ls - lt + lv;
            myStr ns(lns);
            for (int k = 0; k < i; k++) {
              ns.data[k] = s.data[k];
          }
           for (int k = i; k <= i + lv - 1; k++) {
              ns.data[k] = v.data[k - i];
           }
            for (int k = i+lv; k <= lns - 1; k++) {
               ns.data[k] = s.data[k - lv + lt];
          }
          s = ns;
            return 1;
        }
    }
    return 0;
}

myMatrix::myMatrix(const int&row, const int&col, const int&num, const int*p) {
    rowNum = row;
    colNum = col;
    nodeNum = num;
    nodeList = new matrixNode [nodeNum];
    for (int i = 0; i < 3*num; i++) {
        if (i % 3 == 0) {
            nodeList[i/3].row = p[i];
        }
        if (i % 3 == 1) {
            nodeList[i/3].col = p[i];
        }
        if (i % 3 == 2) {
            nodeList[i/3].value = p[i];
        }
    }
    tide();
}
myMatrix::~myMatrix() {

}
myMatrix::myMatrix() {

}
myMatrix::myMatrix(const int&row, const int&col, const int&num) {
    rowNum = row;
    colNum = col;
    nodeNum = num;
    nodeList = new matrixNode[nodeNum];
}
bool myMatrix::left_big(int a, int b) {
    if ((nodeList[a].row > nodeList[b].row)|| ((nodeList[a].row == nodeList[b].row)&& (nodeList[a].col > nodeList[b].col)))
        return 1;
    return 0;
}
void myMatrix::tide() {
    matrixNode x;
    for (int i = 0; i < nodeNum-1; i++) {
        for (int j = 0; j <= nodeNum - i - 2; j++) {
            if (left_big(j, j + 1)) {
                x = nodeList[j];
                nodeList[j] = nodeList[j + 1];
                nodeList[j + 1] = x;
            }
        }
    }

}
void myMatrix::FastTransposeSMatrix(myMatrix&m) {
   
    myMatrix nm(rowNum, colNum, nodeNum);
    for (int i = 0; i < nm.nodeNum; i++) {
        nm.nodeList[i].col = nodeList[i].row;
        nm.nodeList[i].row = nodeList[i].col;
        nm.nodeList[i].value = nodeList[i].value;
    }
    
    nm.colNum = rowNum;
    nm.rowNum = colNum;
    
    nm.tide();
    m = nm;
        
}
void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
